// https://leetcode.cn/problems/pacific-atlantic-water-flow/

// 题干：有一个 m × n 的矩形岛屿，与 太平洋 和 大西洋 相邻。 “太平洋” 处于大陆的左边界和上边界，而 “大西洋” 处于大陆的右边界和下边界。
//       这个岛被分割成一个由若干方形单元格组成的网格。
//       给定一个 m x n 的整数矩阵 heights ， heights[r][c] 表示坐标 (r, c) 上单元格 高于海平面的高度 。
//       岛上雨水较多，如果相邻单元格的高度 小于或等于 当前单元格的高度，雨水可以直接向北、南、东、西流向相邻单元格。水可以从海洋附近的任何单元格流入海洋。
//       返回网格坐标 result 的 2D 列表 ，
//       其中 result[i] = [ri, ci] 表示雨水从单元格 (ri, ci) 流动 既可流向太平洋也可流向大西洋 。

// 示例：输入: heights = [[2,1],[1,2]]
//       输出: [[0,0],[0,1],[1,0],[1,1]]

// 碎语：题目意思就是求出哪些点能流向大西洋，又能流向太平洋
//       第一种解法是直接判断，拿到一个点就判断，可以但超时
//       正难则反，我们从海洋开始，判断大西洋和太平洋能范围到哪里，从而选出那些被两个海洋范围到的单元格
//       时间复杂度由O(m^2*n^2)变为O(m*n)
//       这是因为第二种方法的点不会走第三次，最多就是大西洋走一次，太平洋走一次

#include <bits/stdc++.h>
using namespace std;

class Solution
{
    bool visPacific[201][201];
    bool visAtlantic[201][201];
    int m, n;
    vector<vector<int>> ret;
public:
    int dx[4] ={-1,1,0,0};
    int dy[4] = {0,0,-1,1};

    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights)
    {
        m = heights.size(), n = heights[0].size();
        memset(visPacific, 0, sizeof(visPacific));
        memset(visAtlantic, 0, sizeof(visAtlantic));

        // 1.太平洋深搜
        for (int j = 0 ; j < n ; j++){
            visPacific[0][j] = true;
            dfsP(heights, 0, j);
        }

        for (int i = 0 ; i < m ; i++){
            visPacific[i][0] = true;
            dfsP(heights, i, 0);
        }

        // 2.大西洋深搜
        for (int j = 0 ; j < n ; j++){
            visAtlantic[m - 1][j] = true;
            dfsA(heights, m - 1, j);
        }

        for (int i = 0 ; i < m ; i++){
            visAtlantic[i][n - 1] = true;
            dfsA(heights, i, n - 1);
        }

        // 3.收集答案
        for (int i = 0 ; i < m ; i++){
            for (int j = 0 ; j < n ; j++){
                if (visAtlantic[i][j] && visPacific[i][j]) ret.push_back({i,j});
            }
        }

        return ret;
    }

    void dfsP(vector<vector<int>>& heights, int i, int j)
    {
        for (int k = 0 ; k < 4 ; k++){
            int x = i + dx[k], y = j + dy[k];

            if (x >= 0 && x < m && y >= 0 && y < n && !visPacific[x][y] && heights[x][y] >= heights[i][j]){
                visPacific[x][y] = true;

                dfsP(heights, x, y);
            }
        }
    }

    void dfsA(vector<vector<int>>& heights, int i, int j)
    {
        for (int k = 0 ; k < 4 ; k++){
            int x = i + dx[k], y = j + dy[k];

            if (x >= 0 && x < m && y >= 0 && y < n && !visAtlantic[x][y] && heights[x][y] >= heights[i][j]){
                visAtlantic[x][y] = true;

                dfsA(heights, x, y);
            }
        }
    }
};

int main()
{
    Solution sol;
    vector<vector<int>> heights = {{2,1},{1,2}};

    vector<vector<int>> index = sol.pacificAtlantic(heights);

    for (const auto& arr : index){
        for (const auto& num : arr){
            cout << num << " ";
        }
        cout << endl;
    }

    return 0;
}